package com.ai.zuochengyun.phase01.class04;

import java.util.PriorityQueue;

public class Code03_LessMoneySplitGold {

    public static void main(String[] args) {
//        int testTimes = 10000;
//        int arrLen = 6;
//        for (int i = 0; i < testTimes; i++) {
//            int[] m1 = new int[arrLen];
//            for (int j = 0; j < arrLen; j++) {
//                m1[j] = (int) (Math.random() * 10) + 1;
//            }
//            int[] m2 = new int[arrLen];
//            System.arraycopy(m1, 0, m2, 0, m1.length);
//            int[] m3 = new int[arrLen];
//            System.arraycopy(m1, 0, m3, 0, m1.length);
//
//            int ans1 = splitGold1(m2);
//            int ans2 = splitGold2(m3);
//            if (ans1 != ans2) {
//                for (int j = 0; j < m1.length; j++) {
//                    System.out.print("[" + m1[j] + "]");
//                }
//                System.out.println();
//                System.out.println("ans1=" + ans1 + "--ans2=" + ans2);
//                System.out.println("Oops");
//                break;
//            }
//        }
//        System.out.println("Finish!");

        splitGold1(new int[]{1,2,4});
    }

    private static int splitGold1(int[] golds) {
        return process(golds, 0);
    }

    /**
     * @param golds 等待需要合并的数
     * @param pre   之前的合并行为产生了多少总代价
     * @return
     */
    private static int process(int[] golds, int pre) {
        if (golds.length == 1) {
            return pre;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < golds.length; i++) {
            for (int j = i + 1; j < golds.length; j++) {
                // 本次花的代价
                int merge = golds[i] + golds[j];
                // 剔除参与本次计算的数，并将计算结果加入当前数组
                int[] nexts = copyButExceptOne(golds, i, j);
                // 剩余要参与计算的数组nexts
                // 本次和之前的代价pre + merge
                ans = Math.min(ans, process(nexts, pre + merge));
            }
        }
        return ans;
    }

    private static int[] copyButExceptOne(int[] golds, int i, int j) {
        int[] ans = new int[golds.length - 1];
        int index = 0;
        for (int k = 0; k < golds.length; k++) {
            // 将原始数组中参与计算下标对应的元素剔除
            if (k != i && k != j) {
                ans[index++] = golds[k];
            }
        }
        // 将参与计算的值的和加入数组中
        ans[index] = golds[i] + golds[j];
        return ans;
    }

    private static int splitGold2(int[] golds) {
        if (golds == null || golds.length == 0) {
            return 0;
        }
        // 将所有元素放入小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int ele : golds) {
            heap.add(ele);
        }
        int ans = 0;
        while (!heap.isEmpty() && heap.size() > 1) {
            // 将计算的值放入小根堆
            int cur = heap.poll() + (!heap.isEmpty() ? heap.poll() : 0);
            heap.add(cur);
            // 将当前计算的值计入总代价中
            ans += cur;
        }
        return ans;
    }
}
